import java.util.Scanner;

/**
 * <p>
 * 归并排序
 * </p>
 * <p>
 * 这是一种基于分治思想的排序，不断分块也用到了递归思想，这里我们使用二路归并
 * </p>
 * <p>时间复杂度：nlog(n)</p>
 *
 * @author 没天赋
 * @since 2025-6-15
 */
public class mergeSort {

    public static int n;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        int[] a = new int[n + 5];
        for (int i = 1; i <= n; i++) {
            a[i] = sc.nextInt();
        }
        mergeSort(a, 1, n);
        for (int i = 1; i <= n; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println();
    }

    /**
     * 归并排序方法
     *
     * @param a
     * @param l
     * @param r
     */
    public static void mergeSort(int[] a, int l, int r) {
        // 递归出口，保证往下归并时至少有两个元素
        if (l >= r) {
            return;
        }
        // 二路归并，就是要不断二分
        int mid = (l + r) / 2;
        // 左下
        mergeSort(a, l, mid);
        // 右下
        mergeSort(a, mid + 1, r);
        // 创建临时数组来暂存排序好的数组
        int[] temp = new int[a.length];
        // 左子数组指针，右子数组指针，临时数组指针
        int pl = l, pr = mid + 1, p = l;
        // 要直到一个数组遍历完才结束
        while (pl <= mid && pr <= r) {
            if (a[pl] < a[pr]) {
                temp[p++] = a[pl++];
            } else {
                temp[p++] = a[pr++];
            }
        }
        // 将另外一个没存完的数组全部存入
        while (pl <= mid) {
            temp[p++] = a[pl++];
        }
        while (pr <= r) {
            temp[p++] = a[pr++];
        }
        // 将临时数组中的值拷贝给原数组
        for (int i = l; i <= r; i++) {
            a[i] = temp[i];
        }
    }
}
/**
 * 测试数据 1：
 * 8
 * 8 7 6 5 4 3 2 1
 * ---------------
 * 1 2 3 4 5 6 7 8
 *
 * 测试数据 2：
 * 5
 * 78 99 23 11 5
 * ---------------
 * 5 11 23 78 99
 */